% this file is called up by thesis.tex
% content in this file will be fed into the main document

\chapter{Diffusion under organic dynamics} % top level followed by section, subsection
\label{chapter:discovery}

% ----------------------- contents from here ------------------------

In this chapter, we study diffusion processes under organic dynamics
that are motivated by information discovery in large-scale distributed
networks such as peer-to-peer and social networks.  A well-studied
problem in peer-to-peer networks is {\em resource discovery}, where
the goal for nodes is to discover all other nodes in the network. For
example, a node may want to know the IP addresses of all the other
hosts in the network. In social networks, nodes (people) discover new
nodes through exchanging contacts with their neighbors (friends).  In
both cases the discovery of new nodes changes the underlying network
--- new edges are added to the network --- and the process continues
in the changed network.
  
We study and analyze two natural gossip-based diffusion/discovery
processes.  In the {\em push discovery} or {\em triangulation}
process, each node repeatedly chooses two random neighbors and
connects them (i.e., ``pushes'' their mutual information to each
other). In the {\em pull discovery} process or the {\em two-hop walk},
each node repeatedly requests or ``pulls'' a random contact from a
random neighbor and connects itself to this two-hop neighbor.  Both
processes are lightweight in the sense that the amortized work done
per node is constant per round, local, and naturally robust due to the
inherent randomized nature of gossip.
  
Our main result is an almost-tight analysis of the time taken for
these two randomized processes to converge.  We show that in any
undirected $n$-node graph both processes take $O(n\log^2 n)$ rounds to
connect every node to all other nodes with high probability, whereas
$\Omega(n \log n)$ is a lower bound.  We also study the two-hop walk
in directed graphs, and show that it takes $O(n^2 \log n)$ time with
high probability, and that the worst-case bound is tight for arbitrary
directed graphs, whereas $\Omega(n^2)$ is a lower bound for strongly
connected directed graphs.  A key technical challenge that we overcome
in our work is the analysis of a randomized process that itself
results in a constantly changing network leading to complicated
dependencies in every round.

In Section~\ref{sec:discovery.pre} we list the notations and prove
some common lemmas we will use in the proofs. We show the upper and
lower bounds of the push discovery and the pull discovery in
Section~\ref{sec:discovery.triangulation} and \ref{sec:discovery.2hop}
respectively. Then we give the proofs of upper and lower bound of the
pull discovery in directed graph in
Section~\ref{sec:discovery.directed}. Finally, we conclude in
Section~\ref{sec:discovery.conclusion}.

\input{2_discovery/prerequisite}
\input{2_discovery/triangulation}
\input{2_discovery/2hop}
\input{2_discovery/directed}
\input{2_discovery/discussion}

% ---------------------------------------------------------------------------
% ----------------------- end of thesis sub-document ------------------------
% ---------------------------------------------------------------------------
